#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
  int candy(vector<int> &ratings) {
    int length = ratings.size();

    vector<int> left(length, 0);  // direction of left
    vector<int> right(length, 0); // direction of right

    left[length - 1] = 1;
    for (int i = length - 2; i >= 0; i--) {
      if (ratings[i] <= ratings[i + 1]) {
        left[i] = 1;
      } else {
        left[i] = left[i + 1] + 1;
      }
    }

    right[0] = 1;
    for (int i = 1; i < length; i++) {
      if (ratings[i] <= ratings[i - 1]) {
        right[i] = 1;
      } else {
        right[i] = right[i - 1] + 1;
      }
    }

    int sum = 0;
    int maxVal = 0;
    for (int i = 0; i < length; i++) {

      maxVal = left[i] > right[i] ? left[i] : right[i];
      sum += maxVal;
    }
    return sum;
  }
};

void testcase01() {
  vector<int> input;

  input.push_back(1);
  input.push_back(0);
  input.push_back(2);
  int expect = 5;

  Solution so;
  int got = so.candy(input);

  if (got != expect) {
    printf("failed! expect:%d, but got:%d\n", expect, got);
  }
}
void testcase02() {
  vector<int> input;

  input.push_back(1);
  input.push_back(2);
  input.push_back(2);
  int expect = 4;

  Solution so;
  int got = so.candy(input);

  if (got != expect) {
    printf("failed! expect:%d, but got:%d\n", expect, got);
  }
}

int main() {

  testcase01();
  testcase02();

  return 0;
}
